#include <iostream>
#include <vector>
using namespace std;

const int max_board_size = 64;

struct SubGraph
{
  int x;
  int y;
  int length;
};

struct Board
{
  unsigned long long pos[max_board_size];
  int length_of_side; //边长
  int max_length;
  int count; //子图的数量
  int max_pos;
  int& solution_count;
  vector<SubGraph>& result;
  SubGraph* graphes;  

  Board( int length, int max_length, int& maxcount, vector<SubGraph>& _result ):
   solution_count( maxcount ),
   result( _result )
  {
    this->length_of_side = length;
    this->max_length = max_length;
    this->count = 0;
    this->max_pos = max_board_size * length;
    memset( pos, 0x0, sizeof( pos ) );
    graphes = new SubGraph[length * length];    
  }

  ~Board()
  {
    delete[] graphes;
  }

  inline bool test( int x, int y, int s )
  {
    //if( c.x + s > length_of_side || c.y + s > length_of_side ) return false;
    unsigned long long flag = 1;
    flag = (flag << ( x + s )) - (flag << x);
    if( ( pos[y] & flag ) != 0 ) return false;
    if( ( pos[y + s - 1] & flag ) != 0 ) return false;
    return true;
  }

  inline void cut( int x, int y, int s )
  {
    unsigned long long flag = 1;
    flag = (flag << ( x + s )) - (flag << x);
    for( int i = y; i < y + s; i++ )
    {
      pos[i] |= flag;
    }
    SubGraph& g = graphes[count++];
    g.length = s;
    g.x = x;
    g.y = y;
  }

  inline void tie( int x, int y, int s )
  {
    unsigned long long flag = 1;
    flag = (flag << ( x + s )) - (flag << x);
    flag = ~flag;
    for( int i = y; i < y + s; i++ )
    {
      pos[i] &= flag;
    }    
    count--;
  }

  void split( int pos )
  {
    if( count >= solution_count ) return;

    if( pos == max_pos )
    {
      if( solution_count > count )
      {
        solution_count = count;
        result.clear();
        for( int i = 0; i < count; i++ )
        {
          result.push_back( graphes[i] );
        }
      }
      return;
    }

    int x = pos & ( max_board_size - 1 );
    int y = pos >> 6 ;
    int next = ( x == length_of_side - 1 ) ? ( (y + 1) << 6 ) : pos + 1;


    if( !test( x, y, 1 ) )
    {
      split( next );
      return;
    }

    for( int i = max_length; i >= 1; i-- )
    {
      if( x + i > length_of_side || y + i > length_of_side ) continue;
      if( test( x, y, i ) )
      {
        cut( x, y, i );
        split( next );
        tie( x, y, i );
      }
    }
  }

};

void slove( int n )
{
  int solution = n * n + 1;
  int start = ( n % 2 == 0 ) ? n / 2 : n / 2 + 1;

  vector<SubGraph> result;
  
  for( int i = start; i < n; i++ )
  {
    Board t( n, i, solution, result );
    t.cut( 0, 0, i );
    for( int j = 0; j < i / ( n - i ); j++ )
    {
      t.cut( j * ( n - i ), i, n - i );
      t.cut( i , j * ( n - i ), n - i ); 
    }
    t.split( 0 );
  }

  cout << result.size() << endl;
  for( vector<SubGraph>::const_iterator it = result.begin(); it != result.end(); it++ )
  {
    cout << it->x + 1 << " " << it->y + 1 << " " << it->length << endl;
  }
}

int main()
{
  int cases = 0;
  cin >> cases;
  while( cases-- )
  {
    int n = 0;
    cin >> n;
    slove( n );
  }
}
